题意简述：
求$a^b$的所有因子和
解题思路：
既然要求因子和，那我们必然要先分解质因数
根据整数的唯一分解定理，整数a进行质因数分解对应的式子唯一，有:
$$a = p_1^{k_1} * p_2^{k_2} *p_3^{k_3}* … * p_n^{k_n}$$
又因为本题要分解的是$a^b$，所以上面的式子又可以写成这样：
$$a^b= p_1^{k_1*b} * p_2^{k_2*b} *p_3^{k_3*b}* … * p_n^{k_n*b}$$
证明很简单，就是把上面第一个式子乘上$b$次即可得第二个式子
接下来我们要求的是因子和，
所以就有：
$$ans= (1+p_1^1 + p_1^2 +p_1^3+ … + p_1^{k_1*b})*(1+p_2^1 + p_2^2 +p_2^3+ … + p_1^{k_2*b})*…*(1+p_n^1 + p_n^2 +p_n^3+ … + p_n^{k_n*b})$$
对于上面的式子是不是有点熟悉？
对，你没有看错，就是等比数列之间的乘积
根据等比数列求和公式：
$$sum=\frac{p^{n}-1}{p-1}$$
我们就能求出各数列的和，
对于$p^{n+1}$，我们用快速幂求
又因为本题要求的答案要对9901取模
故我们又可以通过逆元将除$p-1$转化为乘$p-1$的逆元
接下来要求逆元，根据定义，在$mod\ p$的意义下，对于一个整数$a$，有：
$$a*x≡1(mod\ p)$$
$x$即为$a$的逆元，反之成立
注意此处的$a,p$均与上文的意义不同，仅作为公式中的未知数
当$a,p$不互质时，逆元不存在，即上面的式子要满足：
$$gcd(a,p)=1$$
那么这个$x$怎么求？
那我们再引入一个定理，费马小定理：
假如$a$是一个整数，$p$是一个质数，那么当$a$是$p$的倍数时，有：
$$a^p≡a(mod\ p)$$
当$a$不是$p$的倍数时，有：
$$a^{p-1}≡1(mod\ p)$$
对于本题，显然我们要用的是第二种情况，第二种情况又可以变形为：
$$a*a^{p-2}≡1(mod\ p)$$
上式恰好对应逆元的定义式，故$a$在$mod\ p$意义下的逆元为$a^{p-2}$
$a^{p-2}$我们用快速幂即可求得
那逆元不存在怎么办，不用担心，因为对应上面的式子$p-1$，有：
$$(p-1) \ mod \ 9901=0$$
即:
$$p \ mod \ 9901=1$$
所以该等比数列之和($mod\ p$意义下)为：
$$sum= 1+({p\ mod\ 9901})^1 +({p\ mod\ 9901})^2 +({p\ mod\ 9901})^3+ … + ({p\ mod\ 9901})^{n}$$
即：
$$sum=1+n$$
至此，本题就分析完了
代码实现：
1 |
|